#pragma once

namespace zzz {
// Column majored sparse matrix
template<typename T>
class SparseMatrix
{
  SparseMatrix():row_(0), col_(0), sorted_(false){}
  SparseMatrix(zuint row, zuint col):row_(row), col_(col), sorted_(false){}
  void Create(zuint row, zuint col) {
    Clear();
    if (row_==row && col_==col) 
      return;
    row_=row;
    col_=col;
  }

  void ClearData() {
    for (zuint i=0; i<v_.size(); i++)
      v_[i].clear();
  }

  void Clear() {
    v_.clear();
  }

  const T& operator()(zuint row, zuint col) const {
    return Get(row, col);
  }

  const T& Get(zuint row, zuint col) const {
    vector<ColumnDataNode>::const_iterator vi;
    if (sorted_)
      vi = std::lower_bound(v_[col].begin(), v_[col].end(), row, RowEqual());
    else
      vector<ColumnDataNode>::const_iterator vi = std::find(v_[col].begin(), v_[col].end(), row, RowEqual());

    if (vi!=v_[col].end())
      return vi->second;
    else
      return ZERO_VALUE;
  }

  T& MustGet(zuint row, zuint col) {
    vector<ColumnDataNode>::const_iterator vi;
    if (sorted_)
      vi = std::lower_bound(v_[col].begin(), v_[col].end(), row, RowEqual());
    else
      vector<ColumnDataNode>::const_iterator vi = std::find(v_[col].begin(), v_[col].end(), row, RowEqual());

    if (vi!=v_[col].end())
      return vi->second;
    else {
      v_[col].push_back(make_pair(row, ZERO_VALUE));
      sorted_=false;
      return v_[col].back();
    }
  }

  void AddData(int row, int col, const T& number) {
    MustGet(row, col) = number;
  }

  void SortColumn() {
    for (zuint i=0; i<v_.size(); i++)
      sort(v_[i].begin(), v_[i].end());
    sorted_=true;
  }


private:
  typedef std::pair<int,double> ColumnDataNode;
  typedef std::vector<ColumnDataNode> ColumnData;
  static T ZERO_VALUE;
  class RowEqual {
    bool operator()(const int row, const ColumnDataNode &node) {return row == node.first;}
  };

  bool sorted_;
  zuint row_, col_;
  vector<ColumnData> v_;
};

template<typename T>
T SparseMatrix::ZERO_VALUE=T(0);

};  // namespace zzz